Computer graphics are being used today to perform a wide variety of tasks. Many different areas of business, industry, government, education, entertainment, and most recently, the home, are tapping into the enormous and rapidly growing list of applications developed for today's increasingly powerful computer devices. Graphical user interfaces have replaced textual interfaces as the standard means for user computer interaction.
Graphics have also become a key technology for communicating ideas, data, and trends in most areas of commerce, science, and education. Until recently, real time user interaction with three dimensional (3D) models and pseudo-realistic images was feasible on only very high performance workstations. These workstations contain dedicated, special purpose graphics hardware. The progress of semiconductor fabrication technology has made it possible to do real time 3D animation, with color shaded images of complex objects, described by thousands of polygons, on powerful dedicated rendering subsystems. The most recent and most powerful workstations are capable of rendering completely life-like, realistically lighted, 3D objects and structures.
In a typical 3D computer generated object, the surfaces of the 3D object are described by data models. These data models store “primitives” (usually mathematically described polygons and polyhedra) that define the shape of the object, the object attributes, and the connectivity and positioning data describing how the objects fit together. The component polygons and polyhedra connect at common edges defined in terms of common vertices and enclosed volumes. The polygons are textured, Z-buffered, and shaded onto an array of pixels, creating a realistic 3D image.
Many applications require the generation of smooth surfaces and smooth curves. To realistically generate a real-world image, the surfaces of objects in the image need to be realistically modeled. The most common representation for 3D surfaces are “polygon meshes.” A polygon mesh is a set of connected, polygonal bounded, planar surfaces. Open boxes, cabinets, and building exteriors can be easily and naturally represented by polygon meshes. Polygon meshes, however, are less easily used to represent objects with curved surfaces.
Referring now to prior art FIG. 1A, a simple polygon mesh of a section 10 of a patch is shown, while prior art FIG. 1B shows an actual section 11 of a patch. Each polygon of the section 10 is a mathematical representation of a corresponding portion of the surface of the section 11. The interconnecting vertices (e.g., vertices 13) and the interconnecting edges of the polygons (e.g., edges 12) collectively define the surface of section 10 in 3D space. There are obvious short comings, however, in the accuracy of the section 10 in comparison to actual section 11. The polygons model the surface of section 11, but the representation is only approximate. The “errors” of the approximation can be made arbitrarily small by using more and more polygons to create an increasingly accurate piecewise linear approximation.
Referring now to prior art FIG. 2A, prior art FIG. 2B, and prior art FIG. 2C, an initial representation 21, an intermediate representation 22, and a final representation 23, are shown respectively. The initial representation 21 is a polygon mesh of a rain drop. As described above, initial representation 21 consists of a fewer number of polygons, leading to a “blocky,” or geometrically aliased, representation of the rain drop. It should be noted that the polygons of initial representation 21 are comprised of triangles, whereas the polygons of section 10 are comprised of quadrilaterals. Regardless of the nature of the polygon primitive (triangle, quadrilateral, and the like) used to model a curved surface, the general properties, e.g., geometric aliasing, are substantially the same.
In proceeding from initial representation 21 to intermediate representation 22, and to final representation 23, the number of polygons in the polygon mesh modeling the rain drop are greatly increased. The final representation 23 contains several orders of magnitude more polygons than initial representation 21. This yields a much more accurate piecewise linear approximation of the rain drop. Computer graphics engineers rely upon a techniques for modeling and manipulating the curved surfaces of the objects (e.g., the rain drop of final representation 23). For engineering and computer aided design applications, it is often highly advantageous to have as accurate a model as possible.
For example, engineers modeling the surface of the exterior body of an automobile, or modeling a new mechanical part for a jet engine, desire models which are as accurate as possible. The models should enable accurate visualization of their designs. The models should also be easily manipulated and transformed, allowing engineers to alter a design, visualize the result of the alteration, and subsequently alter the design again.
While modeling objects with curved surfaces can be accomplished using polygon meshes having very large numbers of polygons, such models are computationally very unwieldy. If an object is stored as a large polygon mesh, the demands upon the data transfer bandwidth of the workstations, the demands upon the processor power, demands upon memory for storing such models, and other such problems, combine to make fast easy intuitive 3D interaction and iterative design alteration very slow (if not impossible). As a result, the 3D workstation industry utilizes mathematical parametric representations of the curved surfaces of an object to define and model the object. Parametric models also allow an artist or designer to easily manipulate the global shapes of surfaces through a small number of interactions. Polyhedral models are computationally very intensive, requiring many vertices to be repositioned for even a minor change in the overall shape of the modeled object.
In a parametric representation, the curves of an object (e.g., the rain drop of FIG. 2) are defined mathematically using equations. The equations collectively form what is referred to as a parametric representation of the object, specifically, the curved surfaces of the object. Parametric representations overcome the problems posed by a polyhedral representation (e.g., a polygon mesh). The actual shape of the object can be very closely approximated using a parametric representation. This representation consumes several orders of magnitude less space than an equivalent polyhedral representation Thus, for example, the rain drop of FIG. 2C can be defined and stored as a parametric representation. This representation can be easily manipulated, easily altered, and easily transformed, among other advantages, in comparison to the polyhedral representation (e.g., final representation 23).
Perhaps the most widely used form of curved surface parametric representation are non-uniform rational B-spline representations (NURBS). NURBS are widely used in the computer aided design (CAD) industry to model curved surfaces. Among their many benefits, NURBS have two important advantages relative to other forms of parametric representation. The first advantage is that they are invariant under projective transformations. The second advantage is that they can very accurately define virtually any curved surface. Thus, NURBS are widely used in the field of 3D CAD. While parametric representations of curved surfaces and NURBS are discussed herein, the mathematical form and characteristics of curved surface parametric representation and NURBS are well known in the art. Those desiring a more extensive description of curved surface parametric representation and NURBS should consult “Gerald Farin, CURVES AND SURFACES FOR COMPUTER AIDED DESIGN, ISBN 0-12-249051-7” which is incorporated herein as background material.
The problem with NURBS, however, is the fact that the NURBS model is not “natively” rendered by the dedicated rendering hardware of prior art 3D graphics workstations. The rendering hardware of typical 3D graphics workstations are designed and optimized to function with polygons. The rendering algorithms, the special purpose rendering hardware, and the display hardware are designed to manipulate and display images generated from polygonal graphics primitives. Thus, the NURBS models need to be transformed using software into polygon meshes prior to rendering. This software executes on the host processor(s) or graphics co-processor(s), operates on the NURBS model, and creates a resulting polygon mesh stored in the memory of the 3D graphics workstation. The resulting polygon mesh is then rendered by the dedicated rendering hardware into a 3D image on a display. When an engineer makes a change to the NURBS model, the parameters of the NURBS model are changed, a new resulting polygon mesh is created, and the changed image is subsequently displayed.
This prior art rendering process, however, is slow. The specific rendering software which transforms the NURBS model into the resulting polygon mesh is computationally very expensive. Large numbers of clock cycles are consumed by the specific rendering software. This greatly detracts from the desired “interactive” quality of modern CAD. Additionally, other programs executing concurrently on the workstation are adversely impacted.
The prior art rendering process makes very large demands on the data transfer bandwidth of the 3D graphics workstation. The specific rendering software executes on the host processor(s) or graphics co-processor(s) and needs to move large amounts of data across the busses of the 3D graphics workstation (e.g., transfers to and from main memory or from graphics co-processors to polygon rasterizer(s)). This also adversely impacts other programs and processes running on the 3D graphics workstation.
In addition, the prior art rendering process does not utilize the dedicated rendering hardware of the 3D graphics workstation. Modern 3D graphics workstations often include very sophisticated and very extensive rendering subsystems. These subsystems are purposely designed to accelerate the 3D graphics rendering process. However, the specific rendering software, as described above, executes on the host processor(s) or graphics co-processor(s) and does not make use of the dedicated rendering hardware until the resulting polygon mesh is completely computed.
Thus, what is needed is a method which radically speeds up the 3D graphics rendering process. The method should greatly speed the process of rendering NURBS models. What is further required is a method which accurately renders NURBS models and does not unduly burden the data transfer bandwidth of the 3D graphics workstation, or consume an inordinate amount of host processor or graphics co-processor clock cycles. The method of the present invention provides a novel solution to the above requirements.